package com.cuz.hot100;

public class Q41MissingFirstPositiveNumber {

    public static void main(String[] args) {
//        System.out.println(firstMissingPositive1(new int[]{3, 0, 1, 10, 7, 5, 6}));
        int[] ints = {3, 4, -1, 1};
        System.out.println(firstMissingPositive2(ints));
    }

    public static int firstMissingPositive1(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        boolean flagOnePresent = false;
        for (int num : nums) {
            if (num == 1) {
                flagOnePresent = true;
                break;
            }
        }
        if (!flagOnePresent) {
            return 1;
        }
        // 1 2 3 4  5 6 7
        // 3 0 1 10 7 5 6===>3 1 1  1 7 5 6
        for (int index = 0; index < nums.length; index++) {
            if (nums[index] <= 0 || nums[index] > nums.length) {
                nums[index] = 1;
            }
        }
        //0 1 2  3 4 5 6    0 1 2   3 4 5 6
        //3 1 1  1 7 5 6 ==>3 1 -1  1 7 5 6
        //                  -3 1 -1 1 7 5 6
        //                  -3 1 -1 1 7 5 -6
        //                  -3 1 -1 1 -7 -5 -6
        for (int index = 0; index < nums.length; index++) {
            int value = Math.abs(nums[index]);
            nums[value - 1] = -Math.abs(nums[value - 1]);
        }
        for (int index = 0; index < nums.length; index++) {
            if (nums[index] > 0) {
                return index + 1;
            }
        }
        return nums.length + 1;
    }


    public static int firstMissingPositive2(int[] nums) {
        //0  1  2  3   4  5  6
        //3  0  1  10  7  5  6
        //1  0  3  10  7  5  6
        //1  0  3  10  6  5  7
        //1  0  3  10  5  6  7
        if (nums == null || nums.length == 0) {
            return 0;
        }
        for (int index = 0; index < nums.length; index++) {
            int value = nums[index];
            while ((value > 0 && value <= nums.length)&&value != index + 1 && nums[value - 1] != value) {
                swap(nums, index, value - 1);
                value = nums[index];
            }
        }
        for (int index = 0; index < nums.length; index++) {
            if (nums[index] != index + 1) {
                return index + 1;
            }
        }
        return nums.length + 1;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
